﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Linq.Expressions;
using System.Reflection;
using System.Reflection.Emit;
using System.Threading;

namespace WX.WMS.Common
{

        public static class DynamicQueryable
        {
            public static IQueryable<T> Where<T>(this IQueryable<T> source, string predicate, params object[] values)
            {
                return (IQueryable<T>)Where((IQueryable)source, predicate, values);
            }

            public static IQueryable Where(this IQueryable source, string predicate, params object[] values)
            {
                if (source == null) throw new ArgumentNullException("source");
                if (predicate == null) throw new ArgumentNullException("predicate");
                LambdaExpression lambda = DynamicExpression.ParseLambda(source.ElementType, typeof(bool), predicate, values);
                return source.Provider.CreateQuery(
                    Expression.Call(
                        typeof(Queryable), "Where",
                        new Type[] { source.ElementType },
                        source.Expression, Expression.Quote(lambda)));
            }

            public static IQueryable Select(this IQueryable source, string selector, params object[] values)
            {
                if (source == null) throw new ArgumentNullException("source");
                if (selector == null) throw new ArgumentNullException("selector");
                LambdaExpression lambda = DynamicExpression.ParseLambda(source.ElementType, null, selector, values);
                return source.Provider.CreateQuery(
                    Expression.Call(
                        typeof(Queryable), "Select",
                        new Type[] { source.ElementType, lambda.Body.Type },
                        source.Expression, Expression.Quote(lambda)));
            }

            public static IQueryable<T> OrderBy<T>(this IQueryable<T> source, string ordering, params object[] values)
            {
                return (IQueryable<T>)OrderBy((IQueryable)source, ordering, values);
            }

            public static IQueryable OrderBy(this IQueryable source, string ordering, params object[] values)
            {
                if (source == null) throw new ArgumentNullException("source");
                if (ordering == null) throw new ArgumentNullException("ordering");
                ParameterExpression[] parameters = new ParameterExpression[] {
                Expression.Parameter(source.ElementType, "") };
                ExpressionParser parser = new ExpressionParser(parameters, ordering, values);
                IEnumerable<DynamicOrdering> orderings = parser.ParseOrdering();
                Expression queryExpr = source.Expression;
                string methodAsc = "OrderBy";
                string methodDesc = "OrderByDescending";
                foreach (DynamicOrdering o in orderings)
                {
                    queryExpr = Expression.Call(
                        typeof(Queryable), o.Ascending ? methodAsc : methodDesc,
                        new Type[] { source.ElementType, o.Selector.Type },
                        queryExpr, Expression.Quote(Expression.Lambda(o.Selector, parameters)));
                    methodAsc = "ThenBy";
                    methodDesc = "ThenByDescending";
                }
                return source.Provider.CreateQuery(queryExpr);
            }

            public static IQueryable Take(this IQueryable source, int count)
            {
                if (source == null) throw new ArgumentNullException("source");
                return source.Provider.CreateQuery(
                    Expression.Call(
                        typeof(Queryable), "Take",
                        new Type[] { source.ElementType },
                        source.Expression, Expression.Constant(count)));
            }

            public static IQueryable Skip(this IQueryable source, int count)
            {
                if (source == null) throw new ArgumentNullException("source");
                return source.Provider.CreateQuery(
                    Expression.Call(
                        typeof(Queryable), "Skip",
                        new Type[] { source.ElementType },
                        source.Expression, Expression.Constant(count)));
            }

            public static IQueryable GroupBy(this IQueryable source, string keySelector, string elementSelector, params object[] values)
            {
                if (source == null) throw new ArgumentNullException("source");
                if (keySelector == null) throw new ArgumentNullException("keySelector");
                if (elementSelector == null) throw new ArgumentNullException("elementSelector");
                LambdaExpression keyLambda = DynamicExpression.ParseLambda(source.ElementType, null, keySelector, values);
                LambdaExpression elementLambda = DynamicExpression.ParseLambda(source.ElementType, null, elementSelector, values);
                return source.Provider.CreateQuery(
                    Expression.Call(
                        typeof(Queryable), "GroupBy",
                        new Type[] { source.ElementType, keyLambda.Body.Type, elementLambda.Body.Type },
                        source.Expression, Expression.Quote(keyLambda), Expression.Quote(elementLambda)));
            }

            public static bool Any(this IQueryable source)
            {
                if (source == null) throw new ArgumentNullException("source");
                return (bool)source.Provider.Execute(
                    Expression.Call(
                        typeof(Queryable), "Any",
                        new Type[] { source.ElementType }, source.Expression));
            }

            public static int Count(this IQueryable source)
            {
                if (source == null) throw new ArgumentNullException("source");
                return (int)source.Provider.Execute(
                    Expression.Call(
                        typeof(Queryable), "Count",
                        new Type[] { source.ElementType }, source.Expression));
            }
        }

        public abstract class DynamicClass
        {
            public override string ToString()
            {
                PropertyInfo[] props = this.GetType().GetProperties(BindingFlags.Instance | BindingFlags.Public);
                StringBuilder sb = new StringBuilder();
                sb.Append("{");
                for (int i = 0; i < props.Length; i++)
                {
                    if (i > 0) sb.Append(", ");
                    sb.Append(props[i].Name);
                    sb.Append("=");
                    sb.Append(props[i].GetValue(this, null));
                }
                sb.Append("}");
                return sb.ToString();
            }
        }

        public class DynamicProperty
        {
            string name;
            Type type;

            public DynamicProperty(string name, Type type)
            {
                if (name == null) throw new ArgumentNullException("name");
                if (type == null) throw new ArgumentNullException("type");
                this.name = name;
                this.type = type;
            }

            public string Name
            {
                get { return name; }
            }

            public Type Type
            {
                get { return type; }
            }
        }

        public static class DynamicExpression
        {
            public static Expression Parse(Type resultType, string expression, params object[] values)
            {
                ExpressionParser parser = new ExpressionParser(null, expression, values);
                return parser.Parse(resultType);
            }

            public static LambdaExpression ParseLambda(Type itType, Type resultType, string expression, params object[] values)
            {
                return ParseLambda(new ParameterExpression[] { Expression.Parameter(itType, "") }, resultType, expression, values);
            }

            public static LambdaExpression ParseLambda(ParameterExpression[] parameters, Type resultType, string expression, params object[] values)
            {
                ExpressionParser parser = new ExpressionParser(parameters, expression, values);
                return Expression.Lambda(parser.Parse(resultType), parameters);
            }

            public static Expression<Func<T, S>> ParseLambda<T, S>(string expression, params object[] values)
            {
                return (Expression<Func<T, S>>)ParseLambda(typeof(T), typeof(S), expression, values);
            }

            public static Type CreateClass(params DynamicProperty[] properties)
            {
                return ClassFactory.Instance.GetDynamicClass(properties);
            }

            public static Type CreateClass(IEnumerable<DynamicProperty> properties)
            {
                return ClassFactory.Instance.GetDynamicClass(properties);
            }
        }

        internal class DynamicOrdering
        {
            public Expression Selector;
            public bool Ascending;
        }

        internal class Signature : IEquatable<Signature>
        {
            public DynamicProperty[] properties;
            public int hashCode;

            public Signature(IEnumerable<DynamicProperty> properties)
            {
                this.properties = properties.ToArray();
                hashCode = 0;
                foreach (DynamicProperty p in properties)
                {
                    hashCode ^= p.Name.GetHashCode() ^ p.Type.GetHashCode();
                }
            }

            public override int GetHashCode()
            {
                return hashCode;
            }

            public override bool Equals(object obj)
            {
                return obj is Signature ? Equals((Signature)obj) : false;
            }

            public bool Equals(Signature other)
            {
                if (properties.Length != other.properties.Length) return false;
                for (int i = 0; i < properties.Length; i++)
                {
                    if (properties[i].Name != other.properties[i].Name ||
                        properties[i].Type != other.properties[i].Type) return false;
                }
                return true;
            }
        }

        internal class ClassFactory
        {
            public static readonly ClassFactory Instance = new ClassFactory();

            static ClassFactory() { }  // Trigger lazy initialization of static fields

            ModuleBuilder module;
            Dictionary<Signature, Type> classes;
            int classCount;
            ReaderWriterLock rwLock;

            private ClassFactory()
            {
                AssemblyName name = new AssemblyName("DynamicClasses");
                AssemblyBuilder assembly = AppDomain.CurrentDomain.DefineDynamicAssembly(name, AssemblyBuilderAccess.Run);
#if ENABLE_LINQ_PARTIAL_TRUST
            new ReflectionPermission(PermissionState.Unrestricted).Assert();
#endif
                try
                {
                    module = assembly.DefineDynamicModule("Module");
                }
                finally
                {
#if ENABLE_LINQ_PARTIAL_TRUST
                PermissionSet.RevertAssert();
#endif
                }
                classes = new Dictionary<Signature, Type>();
                rwLock = new ReaderWriterLock();
            }

            public Type GetDynamicClass(IEnumerable<DynamicProperty> properties)
            {
                rwLock.AcquireReaderLock(Timeout.Infinite);
                try
                {
                    Signature signature = new Signature(properties);
                    Type type;
                    if (!classes.TryGetValue(signature, out type))
                    {
                        type = CreateDynamicClass(signature.properties);
                        classes.Add(signature, type);
                    }
                    return type;
                }
                finally
                {
                    rwLock.ReleaseReaderLock();
                }
            }

            Type CreateDynamicClass(DynamicProperty[] properties)
            {
                LockCookie cookie = rwLock.UpgradeToWriterLock(Timeout.Infinite);
                try
                {
                    string typeName = "DynamicClass" + (classCount + 1);
#if ENABLE_LINQ_PARTIAL_TRUST
                new ReflectionPermission(PermissionState.Unrestricted).Assert();
#endif
                    try
                    {
                        TypeBuilder tb = this.module.DefineType(typeName, TypeAttributes.Class |
                            TypeAttributes.Public, typeof(DynamicClass));
                        FieldInfo[] fields = GenerateProperties(tb, properties);
                        GenerateEquals(tb, fields);
                        GenerateGetHashCode(tb, fields);
                        Type result = tb.CreateType();
                        classCount++;
                        return result;
                    }
                    finally
                    {
#if ENABLE_LINQ_PARTIAL_TRUST
                    PermissionSet.RevertAssert();
#endif
                    }
                }
                finally
                {
                    rwLock.DowngradeFromWriterLock(ref cookie);
                }
            }

            FieldInfo[] GenerateProperties(TypeBuilder tb, DynamicProperty[] properties)
            {
                FieldInfo[] fields = new FieldBuilder[properties.Length];
                for (int i = 0; i < properties.Length; i++)
                {
                    DynamicProperty dp = properties[i];
                    FieldBuilder fb = tb.DefineField("_" + dp.Name, dp.Type, FieldAttributes.Private);
                    PropertyBuilder pb = tb.DefineProperty(dp.Name, PropertyAttributes.HasDefault, dp.Type, null);
                    MethodBuilder mbGet = tb.DefineMethod("get_" + dp.Name,
                        MethodAttributes.Public | MethodAttributes.SpecialName | MethodAttributes.HideBySig,
                        dp.Type, Type.EmptyTypes);
                    ILGenerator genGet = mbGet.GetILGenerator();
                    genGet.Emit(OpCodes.Ldarg_0);
                    genGet.Emit(OpCodes.Ldfld, fb);
                    genGet.Emit(OpCodes.Ret);
                    MethodBuilder mbSet = tb.DefineMethod("set_" + dp.Name,
                        MethodAttributes.Public | MethodAttributes.SpecialName | MethodAttributes.HideBySig,
                        null, new Type[] { dp.Type });
                    ILGenerator genSet = mbSet.GetILGenerator();
                    genSet.Emit(OpCodes.Ldarg_0);
                    genSet.Emit(OpCodes.Ldarg_1);
                    genSet.Emit(OpCodes.Stfld, fb);
                    genSet.Emit(OpCodes.Ret);
                    pb.SetGetMethod(mbGet);
                    pb.SetSetMethod(mbSet);
                    fields[i] = fb;
                }
                return fields;
            }

            void GenerateEquals(TypeBuilder tb, FieldInfo[] fields)
            {
                MethodBuilder mb = tb.DefineMethod("Equals",
                    MethodAttributes.Public | MethodAttributes.ReuseSlot |
                    MethodAttributes.Virtual | MethodAttributes.HideBySig,
                    typeof(bool), new Type[] { typeof(object) });
                ILGenerator gen = mb.GetILGenerator();
                LocalBuilder other = gen.DeclareLocal(tb);
                Label next = gen.DefineLabel();
                gen.Emit(OpCodes.Ldarg_1);
                gen.Emit(OpCodes.Isinst, tb);
                gen.Emit(OpCodes.Stloc, other);
                gen.Emit(OpCodes.Ldloc, other);
                gen.Emit(OpCodes.Brtrue_S, next);
                gen.Emit(OpCodes.Ldc_I4_0);
                gen.Emit(OpCodes.Ret);
                gen.MarkLabel(next);
                foreach (FieldInfo field in fields)
                {
                    Type ft = field.FieldType;
                    Type ct = typeof(EqualityComparer<>).MakeGenericType(ft);
                    next = gen.DefineLabel();
                    gen.EmitCall(OpCodes.Call, ct.GetMethod("get_Default"), null);
                    gen.Emit(OpCodes.Ldarg_0);
                    gen.Emit(OpCodes.Ldfld, field);
                    gen.Emit(OpCodes.Ldloc, other);
                    gen.Emit(OpCodes.Ldfld, field);
                    gen.EmitCall(OpCodes.Callvirt, ct.GetMethod("Equals", new Type[] { ft, ft }), null);
                    gen.Emit(OpCodes.Brtrue_S, next);
                    gen.Emit(OpCodes.Ldc_I4_0);
                    gen.Emit(OpCodes.Ret);
                    gen.MarkLabel(next);
                }
                gen.Emit(OpCodes.Ldc_I4_1);
                gen.Emit(OpCodes.Ret);
            }

            void GenerateGetHashCode(TypeBuilder tb, FieldInfo[] fields)
            {
                MethodBuilder mb = tb.DefineMethod("GetHashCode",
                    MethodAttributes.Public | MethodAttributes.ReuseSlot |
                    MethodAttributes.Virtual | MethodAttributes.HideBySig,
                    typeof(int), Type.EmptyTypes);
                ILGenerator gen = mb.GetILGenerator();
                gen.Emit(OpCodes.Ldc_I4_0);
                foreach (FieldInfo field in fields)
                {
                    Type ft = field.FieldType;
                    Type ct = typeof(EqualityComparer<>).MakeGenericType(ft);
                    gen.EmitCall(OpCodes.Call, ct.GetMethod("get_Default"), null);
                    gen.Emit(OpCodes.Ldarg_0);
                    gen.Emit(OpCodes.Ldfld, field);
                    gen.EmitCall(OpCodes.Callvirt, ct.GetMethod("GetHashCode", new Type[] { ft }), null);
                    gen.Emit(OpCodes.Xor);
                }
                gen.Emit(OpCodes.Ret);
            }
        }

        public sealed class ParseException : Exception
        {
            int position;

            public ParseException(string message, int position)
                : base(message)
            {
                this.position = position;
            }

            public int Position
            {
                get { return position; }
            }

            public override string ToString()
            {
                return string.Format(Res.ParseExceptionFormat, Message, position);
            }
        }

        internal class ExpressionParser
        {
            struct Token
            {
                public TokenId id;
                public string text;
                public int pos;
            }

            enum TokenId
            {
                Unknown,
                End,
                Identifier,
                StringLiteral,
                IntegerLiteral,
                RealLiteral,
                Exclamation,
                Percent,
                Amphersand,
                OpenParen,
                CloseParen,
                Asterisk,
                Plus,
                Comma,
                Minus,
                Dot,
                Slash,
                Colon,
                LessThan,
                Equal,
                GreaterThan,
                Question,
                OpenBracket,
                CloseBracket,
                Bar,
                ExclamationEqual,
                DoubleAmphersand,
                LessThanEqual,
                LessGreater,
                DoubleEqual,
                GreaterThanEqual,
                DoubleBar
            }

            interface ILogicalSignatures
            {
                void F(bool x, bool y);
                void F(bool? x, bool? y);
            }

            interface IArithmeticSignatures
            {
                void F(int x, int y);
                void F(uint x, uint y);
                void F(long x, long y);
                void F(ulong x, ulong y);
                void F(float x, float y);
                void F(double x, double y);
                void F(decimal x, decimal y);
                void F(int? x, int? y);
                void F(uint? x, uint? y);
                void F(long? x, long? y);
                void F(ulong? x, ulong? y);
                void F(float? x, float? y);
                void F(double? x, double? y);
                void F(decimal? x, decimal? y);
            }

            interface IRelationalSignatures : IArithmeticSignatures
            {
                void F(string x, string y);
                void F(char x, char y);
                void F(DateTime x, DateTime y);
                void F(TimeSpan x, TimeSpan y);
                void F(char? x, char? y);
                void F(DateTime? x, DateTime? y);
                void F(TimeSpan? x, TimeSpan? y);
            }

            interface IEqualitySignatures : IRelationalSignatures
            {
                void F(bool x, bool y);
                void F(bool? x, bool? y);
            }

            interface IAddSignatures : IArithmeticSignatures
            {
                void F(DateTime x, TimeSpan y);
                void F(TimeSpan x, TimeSpan y);
                void F(DateTime? x, TimeSpan? y);
                void F(TimeSpan? x, TimeSpan? y);
            }

            interface ISubtractSignatures : IAddSignatures
            {
                void F(DateTime x, DateTime y);
                void F(DateTime? x, DateTime? y);
            }

            interface INegationSignatures
            {
                void F(int x);
                void F(long x);
                void F(float x);
                void F(double x);
                void F(decimal x);
                void F(int? x);
                void F(long? x);
                void F(float? x);
                void F(double? x);
                void F(decimal? x);
            }

            interface INotSignatures
            {
                void F(bool x);
                void F(bool? x);
            }

            interface IEnumerableSignatures
            {
                void Where(bool predicate);
                void Any();
                void Any(bool predicate);
                void All(bool predicate);
                void Count();
                void Count(bool predicate);
                void Min(object selector);
                void Max(object selector);
                void Sum(int selector);
                void Sum(int? selector);
                void Sum(long selector);
                void Sum(long? selector);
                void Sum(float selector);
                void Sum(float? selector);
                void Sum(double selector);
                void Sum(double? selector);
                void Sum(decimal selector);
                void Sum(decimal? selector);
                void Average(int selector);
                void Average(int? selector);
                void Average(long selector);
                void Average(long? selector);
                void Average(float selector);
                void Average(float? selector);
                void Average(double selector);
                void Average(double? selector);
                void Average(decimal selector);
                void Average(decimal? selector);
            }

            static readonly Type[] predefinedTypes = {
            typeof(Object),
            typeof(Boolean),
            typeof(Char),
            typeof(String),
            typeof(SByte),
            typeof(Byte),
            typeof(Int16),
            typeof(UInt16),
            typeof(Int32),
            typeof(UInt32),
            typeof(Int64),
            typeof(UInt64),
            typeof(Single),
            typeof(Double),
            typeof(Decimal),
            typeof(DateTime),
            typeof(TimeSpan),
            typeof(Guid),
            typeof(Math),
            typeof(Convert)
        };

            static readonly Expression trueLiteral = Expression.Constant(true);
            static readonly Expression falseLiteral = Expression.Constant(false);
            static readonly Expression nullLiteral = Expression.Constant(null);

            static readonly string keywordIt = "it";
            static readonly string keywordIif = "iif";
            static readonly string keywordNew = "new";

            static Dictionary<string, object> keywords;

            Dictionary<string, object> symbols;
            IDictionary<string, object> externals;
            Dictionary<Expression, string> literals;
            ParameterExpression it;
            string text;
            int textPos;
            int textLen;
            char ch;
            Token token;

            public ExpressionParser(ParameterExpression[] parameters, string expression, object[] values)
            {
                if (expression == null) throw new ArgumentNullException("expression");
                if (keywords == null) keywords = CreateKeywords();
                symbols = new Dictionary<string, object>(StringComparer.OrdinalIgnoreCase);
                literals = new Dictionary<Expression, string>();
                if (parameters != null) ProcessParameters(parameters);
                if (values != null) ProcessValues(values);
                text = expression;
                textLen = text.Length;
                SetTextPos(0);
                NextToken();
            }

            void ProcessParameters(ParameterExpression[] parameters)
            {
                foreach (ParameterExpression pe in parameters)
                    if (!String.IsNullOrEmpty(pe.Name))
                        AddSymbol(pe.Name, pe);
                if (parameters.Length == 1 && String.IsNullOrEmpty(parameters[0].Name))
                    it = parameters[0];
            }

            void ProcessValues(object[] values)
            {
                for (int i = 0; i < values.Length; i++)
                {
                    object value = values[i];
                    if (i == values.Length - 1 && value is IDictionary<string, object>)
                    {
                        externals = (IDictionary<string, object>)value;
                    }
                    else
                    {
                        AddSymbol("@" + i.ToString(System.Globalization.CultureInfo.InvariantCulture), value);
                    }
                }
            }

            void AddSymbol(string name, object value)
            {
                if (symbols.ContainsKey(name))
                    throw ParseError(Res.DuplicateIdentifier, name);
                symbols.Add(name, value);
            }

            public Expression Parse(Type resultType)
            {
                int exprPos = token.pos;
                Expression expr = ParseExpression();
                if (resultType != null)
                    if ((expr = PromoteExpression(expr, resultType, true)) == null)
                        throw ParseError(exprPos, Res.ExpressionTypeMismatch, GetTypeName(resultType));
                ValidateToken(TokenId.End, Res.SyntaxError);
                return expr;
            }

#pragma warning disable 0219
            public IEnumerable<DynamicOrdering> ParseOrdering()
            {
                List<DynamicOrdering> orderings = new List<DynamicOrdering>();
                while (true)
                {
                    Expression expr = ParseExpression();
                    bool ascending = true;
                    if (TokenIdentifierIs("asc") || TokenIdentifierIs("ascending"))
                    {
                        NextToken();
                    }
                    else if (TokenIdentifierIs("desc") || TokenIdentifierIs("descending"))
                    {
                        NextToken();
                        ascending = false;
                    }
                    orderings.Add(new DynamicOrdering { Selector = expr, Ascending = ascending });
                    if (token.id != TokenId.Comma) break;
                    NextToken();
                }
                ValidateToken(TokenId.End, Res.SyntaxError);
                return orderings;
            }
#pragma warning restore 0219

            // ?: operator
            Expression ParseExpression()
            {
                int errorPos = token.pos;
                Expression expr = ParseLogicalOr();
                if (token.id == TokenId.Question)
                {
                    NextToken();
                    Expression expr1 = ParseExpression();
                    ValidateToken(TokenId.Colon, Res.ColonExpected);
                    NextToken();
                    Expression expr2 = ParseExpression();
                    expr = GenerateConditional(expr, expr1, expr2, errorPos);
                }
                return expr;
            }

            // ||, or operator
            Expression ParseLogicalOr()
            {
                Expression left = ParseLogicalAnd();
                while (token.id == TokenId.DoubleBar || TokenIdentifierIs("or"))
                {
                    Token op = token;
                    NextToken();
                    Expression right = ParseLogicalAnd();
                    CheckAndPromoteOperands(typeof(ILogicalSignatures), op.text, ref left, ref right, op.pos);
                    left = Expression.OrElse(left, right);
                }
                return left;
            }

            // &&, and operator
            Expression ParseLogicalAnd()
            {
                Expression left = ParseComparison();
                while (token.id == TokenId.DoubleAmphersand || TokenIdentifierIs("and"))
                {
                    Token op = token;
                    NextToken();
                    Expression right = ParseComparison();
                    CheckAndPromoteOperands(typeof(ILogicalSignatures), op.text, ref left, ref right, op.pos);
                    left = Expression.AndAlso(left, right);
                }
                return left;
            }

            // =, ==, !=, <>, >, >=, <, <= operators
            Expression ParseComparison()
            {
                Expression left = ParseAdditive();
                while (token.id == TokenId.Equal || token.id == TokenId.DoubleEqual ||
                    token.id == TokenId.ExclamationEqual || token.id == TokenId.LessGreater ||
                    token.id == TokenId.GreaterThan || token.id == TokenId.GreaterThanEqual ||
                    token.id == TokenId.LessThan || token.id == TokenId.LessThanEqual)
                {
                    Token op = token;
                    NextToken();
                    Expression right = ParseAdditive();
                    bool isEquality = op.id == TokenId.Equal || op.id == TokenId.DoubleEqual ||
                        op.id == TokenId.ExclamationEqual || op.id == TokenId.LessGreater;
                    if (isEquality && !left.Type.IsValueType && !right.Type.IsValueType)
                    {
                        if (left.Type != right.Type)
                        {
                            if (left.Type.IsAssignableFrom(right.Type))
                            {
                                right = Expression.Convert(right, left.Type);
                            }
                            else if (right.Type.IsAssignableFrom(left.Type))
                            {
                                left = Expression.Convert(left, right.Type);
                            }
                            else
                            {
                                throw IncompatibleOperandsError(op.text, left, right, op.pos);
                            }
                        }
                    }
                    else if (IsEnumType(left.Type) || IsEnumType(right.Type))
                    {
                        if (left.Type != right.Type)
                        {
                            Expression e;
                            if ((e = PromoteExpression(right, left.Type, true)) != null)
                            {
                                right = e;
                            }
                            else if ((e = PromoteExpression(left, right.Type, true)) != null)
                            {
                                left = e;
                            }
                            else
                            {
                                throw IncompatibleOperandsError(op.text, left, right, op.pos);
                            }
                        }
                    }
                    else
                    {
                        CheckAndPromoteOperands(isEquality ? typeof(IEqualitySignatures) : typeof(IRelationalSignatures),
                            op.text, ref left, ref right, op.pos);
                    }
                    switch (op.id)
                    {
                        case TokenId.Equal:
                        case TokenId.DoubleEqual:
                            left = GenerateEqual(left, right);
                            break;
                        case TokenId.ExclamationEqual:
                        case TokenId.LessGreater:
                            left = GenerateNotEqual(left, right);
                            break;
                        case TokenId.GreaterThan:
                            left = GenerateGreaterThan(left, right);
                            break;
                        case TokenId.GreaterThanEqual:
                            left = GenerateGreaterThanEqual(left, right);
                            break;
                        case TokenId.LessThan:
                            left = GenerateLessThan(left, right);
                            break;
                        case TokenId.LessThanEqual:
                            left = GenerateLessThanEqual(left, right);
                            break;
                    }
                }
                return left;
            }

            // +, -, & operators
            Expression ParseAdditive()
            {
                Expression left = ParseMultiplicative();
                while (token.id == TokenId.Plus || token.id == TokenId.Minus ||
                    token.id == TokenId.Amphersand)
                {
                    Token op = token;
                    NextToken();
                    Expression right = ParseMultiplicative();
                    switch (op.id)
                    {
                        case TokenId.Plus:
                            if (left.Type == typeof(string) || right.Type == typeof(string))
                                goto case TokenId.Amphersand;
                            CheckAndPromoteOperands(typeof(IAddSignatures), op.text, ref left, ref right, op.pos);
                            left = GenerateAdd(left, right);
                            break;
                        case TokenId.Minus:
                            CheckAndPromoteOperands(typeof(ISubtractSignatures), op.text, ref left, ref right, op.pos);
                            left = GenerateSubtract(left, right);
                            break;
                        case TokenId.Amphersand:
                            left = GenerateStringConcat(left, right);
                            break;
                    }
                }
                return left;
            }

            // *, /, %, mod operators
            Expression ParseMultiplicative()
            {
                Expression left = ParseUnary();
                while (token.id == TokenId.Asterisk || token.id == TokenId.Slash ||
                    token.id == TokenId.Percent || TokenIdentifierIs("mod"))
                {
                    Token op = token;
                    NextToken();
                    Expression right = ParseUnary();
                    CheckAndPromoteOperands(typeof(IArithmeticSignatures), op.text, ref left, ref right, op.pos);
                    switch (op.id)
                    {
                        case TokenId.Asterisk:
                            left = Expression.Multiply(left, right);
                            break;
                        case TokenId.Slash:
                            left = Expression.Divide(left, right);
                            break;
                        case TokenId.Percent:
                        case TokenId.Identifier:
                            left = Expression.Modulo(left, right);
                            break;
                    }
                }
                return left;
            }

            // -, !, not unary operators
            Expression ParseUnary()
            {
                if (token.id == TokenId.Minus || token.id == TokenId.Exclamation ||
                    TokenIdentifierIs("not"))
                {
                    Token op = token;
                    NextToken();
                    if (op.id == TokenId.Minus && (token.id == TokenId.IntegerLiteral ||
                        token.id == TokenId.RealLiteral))
                    {
                        token.text = "-" + token.text;
                        token.pos = op.pos;
                        return ParsePrimary();
                    }
                    Expression expr = ParseUnary();
                    if (op.id == TokenId.Minus)
                    {
                        CheckAndPromoteOperand(typeof(INegationSignatures), op.text, ref expr, op.pos);
                        expr = Expression.Negate(expr);
                    }
                    else
                    {
                        CheckAndPromoteOperand(typeof(INotSignatures), op.text, ref expr, op.pos);
                        expr = Expression.Not(expr);
                    }
                    return expr;
                }
                return ParsePrimary();
            }

            Expression ParsePrimary()
            {
                Expression expr = ParsePrimaryStart();
                while (true)
                {
                    if (token.id == TokenId.Dot)
                    {
                        NextToken();
                        expr = ParseMemberAccess(null, expr);
                    }
                    else if (token.id == TokenId.OpenBracket)
                    {
                        expr = ParseElementAccess(expr);
                    }
                    else
                    {
                        break;
                    }
                }
                return expr;
            }

            Expression ParsePrimaryStart()
            {
                switch (token.id)
                {
                    case TokenId.Identifier:
                        return ParseIdentifier();
                    case TokenId.StringLiteral:
                        return ParseStringLiteral();
                    case TokenId.IntegerLiteral:
                        return ParseIntegerLiteral();
                    case TokenId.RealLiteral:
                        return ParseRealLiteral();
                    case TokenId.OpenParen:
                        return ParseParenExpression();
                    default:
                        throw ParseError(Res.ExpressionExpected);
                }
            }

            Expression ParseStringLiteral()
            {
                ValidateToken(TokenId.StringLiteral);
                char quote = token.text[0];
                string s = token.text.Substring(1, token.text.Length - 2);
                int start = 0;
                while (true)
                {
                    int i = s.IndexOf(quote, start);
                    if (i < 0) break;
                    s = s.Remove(i, 1);
                    start = i + 1;
                }
                if (quote == '\'')
                {
                    if (s.Length != 1)
                        throw ParseError(Res.InvalidCharacterLiteral);
                    NextToken();
                    return CreateLiteral(s[0], s);
                }
                NextToken();
                return CreateLiteral(s, s);
            }

            Expression ParseIntegerLiteral()
            {
                ValidateToken(TokenId.IntegerLiteral);
                string text = token.text;
                if (text[0] != '-')
                {
                    ulong value;
                    if (!UInt64.TryParse(text, out value))
                        throw ParseError(Res.InvalidIntegerLiteral, text);
                    NextToken();
                    if (value <= (ulong)Int32.MaxValue) return CreateLiteral((int)value, text);
                    if (value <= (ulong)UInt32.MaxValue) return CreateLiteral((uint)value, text);
                    if (value <= (ulong)Int64.MaxValue) return CreateLiteral((long)value, text);
                    return CreateLiteral(value, text);
                }
                else
                {
                    long value;
                    if (!Int64.TryParse(text, out value))
                        throw ParseError(Res.InvalidIntegerLiteral, text);
                    NextToken();
                    if (value >= Int32.MinValue && value <= Int32.MaxValue)
                        return CreateLiteral((int)value, text);
                    return CreateLiteral(value, text);
                }
            }

            Expression ParseRealLiteral()
            {
                ValidateToken(TokenId.RealLiteral);
                string text = token.text;
                object value = null;
                char last = text[text.Length - 1];
                if (last == 'F' || last == 'f')
                {
                    float f;
                    if (Single.TryParse(text.Substring(0, text.Length - 1), out f)) value = f;
                }
                else
                {
                    double d;
                    if (Double.TryParse(text, out d)) value = d;
                }
                if (value == null) throw ParseError(Res.InvalidRealLiteral, text);
                NextToken();
                return CreateLiteral(value, text);
            }

            Expression CreateLiteral(object value, string text)
            {
                ConstantExpression expr = Expression.Constant(value);
                literals.Add(expr, text);
                return expr;
            }

            Expression ParseParenExpression()
            {
                ValidateToken(TokenId.OpenParen, Res.OpenParenExpected);
                NextToken();
                Expression e = ParseExpression();
                ValidateToken(TokenId.CloseParen, Res.CloseParenOrOperatorExpected);
                NextToken();
                return e;
            }

            Expression ParseIdentifier()
            {
                ValidateToken(TokenId.Identifier);
                object value;
                if (keywords.TryGetValue(token.text, out value))
                {
                    if (value is Type) return ParseTypeAccess((Type)value);
                    if (value == (object)keywordIt) return ParseIt();
                    if (value == (object)keywordIif) return ParseIif();
                    if (value == (object)keywordNew) return ParseNew();
                    NextToken();
                    return (Expression)value;
                }
                if (symbols.TryGetValue(token.text, out value) ||
                    externals != null && externals.TryGetValue(token.text, out value))
                {
                    Expression expr = value as Expression;
                    if (expr == null)
                    {
                        expr = Expression.Constant(value);
                    }
                    else
                    {
                        LambdaExpression lambda = expr as LambdaExpression;
                        if (lambda != null) return ParseLambdaInvocation(lambda);
                    }
                    NextToken();
                    return expr;
                }
                if (it != null) return ParseMemberAccess(null, it);
                throw ParseError(Res.UnknownIdentifier, token.text);
            }

            Expression ParseIt()
            {
                if (it == null)
                    throw ParseError(Res.NoItInScope);
                NextToken();
                return it;
            }

            Expression ParseIif()
            {
                int errorPos = token.pos;
                NextToken();
                Expression[] args = ParseArgumentList();
                if (args.Length != 3)
                    throw ParseError(errorPos, Res.IifRequiresThreeArgs);
                return GenerateConditional(args[0], args[1], args[2], errorPos);
            }

            Expression GenerateConditional(Expression test, Expression expr1, Expression expr2, int errorPos)
            {
                if (test.Type != typeof(bool))
                    throw ParseError(errorPos, Res.FirstExprMustBeBool);
                if (expr1.Type != expr2.Type)
                {
                    Expression expr1as2 = expr2 != nullLiteral ? PromoteExpression(expr1, expr2.Type, true) : null;
                    Expression expr2as1 = expr1 != nullLiteral ? PromoteExpression(expr2, expr1.Type, true) : null;
                    if (expr1as2 != null && expr2as1 == null)
                    {
                        expr1 = expr1as2;
                    }
                    else if (expr2as1 != null && expr1as2 == null)
                    {
                        expr2 = expr2as1;
                    }
                    else
                    {
                        string type1 = expr1 != nullLiteral ? expr1.Type.Name : "null";
                        string type2 = expr2 != nullLiteral ? expr2.Type.Name : "null";
                        if (expr1as2 != null && expr2as1 != null)
                            throw ParseError(errorPos, Res.BothTypesConvertToOther, type1, type2);
                        throw ParseError(errorPos, Res.NeitherTypeConvertsToOther, type1, type2);
                    }
                }
                return Expression.Condition(test, expr1, expr2);
            }

            Expression ParseNew()
            {
                NextToken();
                ValidateToken(TokenId.OpenParen, Res.OpenParenExpected);
                NextToken();
                List<DynamicProperty> properties = new List<DynamicProperty>();
                List<Expression> expressions = new List<Expression>();
                while (true)
                {
                    int exprPos = token.pos;
                    Expression expr = ParseExpression();
                    string propName;
                    if (TokenIdentifierIs("as"))
                    {
                        NextToken();
                        propName = GetIdentifier();
                        NextToken();
                    }
                    else
                    {
                        MemberExpression me = expr as MemberExpression;
                        if (me == null) throw ParseError(exprPos, Res.MissingAsClause);
                        propName = me.Member.Name;
                    }
                    expressions.Add(expr);
                    properties.Add(new DynamicProperty(propName, expr.Type));
                    if (token.id != TokenId.Comma) break;
                    NextToken();
                }
                ValidateToken(TokenId.CloseParen, Res.CloseParenOrCommaExpected);
                NextToken();
                Type type = DynamicExpression.CreateClass(properties);
                MemberBinding[] bindings = new MemberBinding[properties.Count];
                for (int i = 0; i < bindings.Length; i++)
                    bindings[i] = Expression.Bind(type.GetProperty(properties[i].Name), expressions[i]);
                return Expression.MemberInit(Expression.New(type), bindings);
            }

            Expression ParseLambdaInvocation(LambdaExpression lambda)
            {
                int errorPos = token.pos;
                NextToken();
                Expression[] args = ParseArgumentList();
                MethodBase method;
                if (FindMethod(lambda.Type, "Invoke", false, args, out method) != 1)
                    throw ParseError(errorPos, Res.ArgsIncompatibleWithLambda);
                return Expression.Invoke(lambda, args);
            }

            Expression ParseTypeAccess(Type type)
            {
                int errorPos = token.pos;
                NextToken();
                if (token.id == TokenId.Question)
                {
                    if (!type.IsValueType || IsNullableType(type))
                        throw ParseError(errorPos, Res.TypeHasNoNullableForm, GetTypeName(type));
                    type = typeof(Nullable<>).MakeGenericType(type);
                    NextToken();
                }
                if (token.id == TokenId.OpenParen)
                {
                    Expression[] args = ParseArgumentList();
                    MethodBase method;
                    switch (FindBestMethod(type.GetConstructors(), args, out method))
                    {
                        case 0:
                            if (args.Length == 1)
                                return GenerateConversion(args[0], type, errorPos);
                            throw ParseError(errorPos, Res.NoMatchingConstructor, GetTypeName(type));
                        case 1:
                            return Expression.New((ConstructorInfo)method, args);
                        default:
                            throw ParseError(errorPos, Res.AmbiguousConstructorInvocation, GetTypeName(type));
                    }
                }
                ValidateToken(TokenId.Dot, Res.DotOrOpenParenExpected);
                NextToken();
                return ParseMemberAccess(type, null);
            }

            Expression GenerateConversion(Expression expr, Type type, int errorPos)
            {
                Type exprType = expr.Type;
                if (exprType == type) return expr;
                if (exprType.IsValueType && type.IsValueType)
                {
                    if ((IsNullableType(exprType) || IsNullableType(type)) &&
                        GetNonNullableType(exprType) == GetNonNullableType(type))
                        return Expression.Convert(expr, type);
                    if ((IsNumericType(exprType) || IsEnumType(exprType)) &&
                        (IsNumericType(type)) || IsEnumType(type))
                        return Expression.ConvertChecked(expr, type);
                }
                if (exprType.IsAssignableFrom(type) || type.IsAssignableFrom(exprType) ||
                    exprType.IsInterface || type.IsInterface)
                    return Expression.Convert(expr, type);
                throw ParseError(errorPos, Res.CannotConvertValue,
                    GetTypeName(exprType), GetTypeName(type));
            }

            Expression ParseMemberAccess(Type type, Expression instance)
            {
                if (instance != null) type = instance.Type;
                int errorPos = token.pos;
                string id = GetIdentifier();
                NextToken();
                if (token.id == TokenId.OpenParen)
                {
                    if (instance != null && type != typeof(string))
                    {
                        Type enumerableType = FindGenericType(typeof(IEnumerable<>), type);
                        if (enumerableType != null)
                        {
                            Type elementType = enumerableType.GetGenericArguments()[0];
                            return ParseAggregate(instance, elementType, id, errorPos);
                        }
                    }
                    Expression[] args = ParseArgumentList();
                    MethodBase mb;
                    switch (FindMethod(type, id, instance == null, args, out mb))
                    {
                        case 0:
                            throw ParseError(errorPos, Res.NoApplicableMethod,
                                id, GetTypeName(type));
                        case 1:
                            MethodInfo method = (MethodInfo)mb;
                            if (!IsPredefinedType(method.DeclaringType))
                                throw ParseError(errorPos, Res.MethodsAreInaccessible, GetTypeName(method.DeclaringType));
                            if (method.ReturnType == typeof(void))
                                throw ParseError(errorPos, Res.MethodIsVoid,
                                    id, GetTypeName(method.DeclaringType));
                            return Expression.Call(instance, (MethodInfo)method, args);
                        default:
                            throw ParseError(errorPos, Res.AmbiguousMethodInvocation,
                                id, GetTypeName(type));
                    }
                }
                else
                {
                    MemberInfo member = FindPropertyOrField(type, id, instance == null);
                    if (member == null)
                        throw ParseError(errorPos, Res.UnknownPropertyOrField,
                            id, GetTypeName(type));
                    return member is PropertyInfo ?
                        Expression.Property(instance, (PropertyInfo)member) :
                        Expression.Field(instance, (FieldInfo)member);
                }
            }

            static Type FindGenericType(Type generic, Type type)
            {
                while (type != null && type != typeof(object))
                {
                    if (type.IsGenericType && type.GetGenericTypeDefinition() == generic) return type;
                    if (generic.IsInterface)
                    {
                        foreach (Type intfType in type.GetInterfaces())
                        {
                            Type found = FindGenericType(generic, intfType);
                            if (found != null) return found;
                        }
                    }
                    type = type.BaseType;
                }
                return null;
            }

            Expression ParseAggregate(Expression instance, Type elementType, string methodName, int errorPos)
            {
                ParameterExpression outerIt = it;
                ParameterExpression innerIt = Expression.Parameter(elementType, "");
                it = innerIt;
                Expression[] args = ParseArgumentList();
                it = outerIt;
                MethodBase signature;
                if (FindMethod(typeof(IEnumerableSignatures), methodName, false, args, out signature) != 1)
                    throw ParseError(errorPos, Res.NoApplicableAggregate, methodName);
                Type[] typeArgs;
                if (signature.Name == "Min" || signature.Name == "Max")
                {
                    typeArgs = new Type[] { elementType, args[0].Type };
                }
                else
                {
                    typeArgs = new Type[] { elementType };
                }
                if (args.Length == 0)
                {
                    args = new Expression[] { instance };
                }
                else
                {
                    args = new Expression[] { instance, Expression.Lambda(args[0], innerIt) };
                }
                return Expression.Call(typeof(Enumerable), signature.Name, typeArgs, args);
            }

            Expression[] ParseArgumentList()
            {
                ValidateToken(TokenId.OpenParen, Res.OpenParenExpected);
                NextToken();
                Expression[] args = token.id != TokenId.CloseParen ? ParseArguments() : new Expression[0];
                ValidateToken(TokenId.CloseParen, Res.CloseParenOrCommaExpected);
                NextToken();
                return args;
            }

            Expression[] ParseArguments()
            {
                List<Expression> argList = new List<Expression>();
                while (true)
                {
                    argList.Add(ParseExpression());
                    if (token.id != TokenId.Comma) break;
                    NextToken();
                }
                return argList.ToArray();
            }

            Expression ParseElementAccess(Expression expr)
            {
                int errorPos = token.pos;
                ValidateToken(TokenId.OpenBracket, Res.OpenParenExpected);
                NextToken();
                Expression[] args = ParseArguments();
                ValidateToken(TokenId.CloseBracket, Res.CloseBracketOrCommaExpected);
                NextToken();
                if (expr.Type.IsArray)
                {
                    if (expr.Type.GetArrayRank() != 1 || args.Length != 1)
                        throw ParseError(errorPos, Res.CannotIndexMultiDimArray);
                    Expression index = PromoteExpression(args[0], typeof(int), true);
                    if (index == null)
                        throw ParseError(errorPos, Res.InvalidIndex);
                    return Expression.ArrayIndex(expr, index);
                }
                else
                {
                    MethodBase mb;
                    switch (FindIndexer(expr.Type, args, out mb))
                    {
                        case 0:
                            throw ParseError(errorPos, Res.NoApplicableIndexer,
                                GetTypeName(expr.Type));
                        case 1:
                            return Expression.Call(expr, (MethodInfo)mb, args);
                        default:
                            throw ParseError(errorPos, Res.AmbiguousIndexerInvocation,
                                GetTypeName(expr.Type));
                    }
                }
            }

            static bool IsPredefinedType(Type type)
            {
                foreach (Type t in predefinedTypes) if (t == type) return true;
                return false;
            }

            static bool IsNullableType(Type type)
            {
                return type.IsGenericType && type.GetGenericTypeDefinition() == typeof(Nullable<>);
            }

            static Type GetNonNullableType(Type type)
            {
                return IsNullableType(type) ? type.GetGenericArguments()[0] : type;
            }

            static string GetTypeName(Type type)
            {
                Type baseType = GetNonNullableType(type);
                string s = baseType.Name;
                if (type != baseType) s += '?';
                return s;
            }

            static bool IsNumericType(Type type)
            {
                return GetNumericTypeKind(type) != 0;
            }

            static bool IsSignedIntegralType(Type type)
            {
                return GetNumericTypeKind(type) == 2;
            }

            static bool IsUnsignedIntegralType(Type type)
            {
                return GetNumericTypeKind(type) == 3;
            }

            static int GetNumericTypeKind(Type type)
            {
                type = GetNonNullableType(type);
                if (type.IsEnum) return 0;
                switch (Type.GetTypeCode(type))
                {
                    case TypeCode.Char:
                    case TypeCode.Single:
                    case TypeCode.Double:
                    case TypeCode.Decimal:
                        return 1;
                    case TypeCode.SByte:
                    case TypeCode.Int16:
                    case TypeCode.Int32:
                    case TypeCode.Int64:
                        return 2;
                    case TypeCode.Byte:
                    case TypeCode.UInt16:
                    case TypeCode.UInt32:
                    case TypeCode.UInt64:
                        return 3;
                    default:
                        return 0;
                }
            }

            static bool IsEnumType(Type type)
            {
                return GetNonNullableType(type).IsEnum;
            }

            void CheckAndPromoteOperand(Type signatures, string opName, ref Expression expr, int errorPos)
            {
                Expression[] args = new Expression[] { expr };
                MethodBase method;
                if (FindMethod(signatures, "F", false, args, out method) != 1)
                    throw ParseError(errorPos, Res.IncompatibleOperand,
                        opName, GetTypeName(args[0].Type));
                expr = args[0];
            }

            void CheckAndPromoteOperands(Type signatures, string opName, ref Expression left, ref Expression right, int errorPos)
            {
                Expression[] args = new Expression[] { left, right };
                MethodBase method;
                if (FindMethod(signatures, "F", false, args, out method) != 1)
                    throw IncompatibleOperandsError(opName, left, right, errorPos);
                left = args[0];
                right = args[1];
            }

            Exception IncompatibleOperandsError(string opName, Expression left, Expression right, int pos)
            {
                return ParseError(pos, Res.IncompatibleOperands,
                    opName, GetTypeName(left.Type), GetTypeName(right.Type));
            }

            MemberInfo FindPropertyOrField(Type type, string memberName, bool staticAccess)
            {
                BindingFlags flags = BindingFlags.Public | BindingFlags.DeclaredOnly |
                    (staticAccess ? BindingFlags.Static : BindingFlags.Instance);
                foreach (Type t in SelfAndBaseTypes(type))
                {
                    MemberInfo[] members = t.FindMembers(MemberTypes.Property | MemberTypes.Field,
                        flags, Type.FilterNameIgnoreCase, memberName);
                    if (members.Length != 0) return members[0];
                }
                return null;
            }

            int FindMethod(Type type, string methodName, bool staticAccess, Expression[] args, out MethodBase method)
            {
                BindingFlags flags = BindingFlags.Public | BindingFlags.DeclaredOnly |
                    (staticAccess ? BindingFlags.Static : BindingFlags.Instance);
                foreach (Type t in SelfAndBaseTypes(type))
                {
                    MemberInfo[] members = t.FindMembers(MemberTypes.Method,
                        flags, Type.FilterNameIgnoreCase, methodName);
                    int count = FindBestMethod(members.Cast<MethodBase>(), args, out method);
                    if (count != 0) return count;
                }
                method = null;
                return 0;
            }

            int FindIndexer(Type type, Expression[] args, out MethodBase method)
            {
                foreach (Type t in SelfAndBaseTypes(type))
                {
                    MemberInfo[] members = t.GetDefaultMembers();
                    if (members.Length != 0)
                    {
                        IEnumerable<MethodBase> methods = members.
                            OfType<PropertyInfo>().
                            Select(p => (MethodBase)p.GetGetMethod()).
                            Where(m => m != null);
                        int count = FindBestMethod(methods, args, out method);
                        if (count != 0) return count;
                    }
                }
                method = null;
                return 0;
            }

            static IEnumerable<Type> SelfAndBaseTypes(Type type)
            {
                if (type.IsInterface)
                {
                    List<Type> types = new List<Type>();
                    AddInterface(types, type);
                    return types;
                }
                return SelfAndBaseClasses(type);
            }

            static IEnumerable<Type> SelfAndBaseClasses(Type type)
            {
                while (type != null)
                {
                    yield return type;
                    type = type.BaseType;
                }
            }

            static void AddInterface(List<Type> types, Type type)
            {
                if (!types.Contains(type))
                {
                    types.Add(type);
                    foreach (Type t in type.GetInterfaces()) AddInterface(types, t);
                }
            }

            class MethodData
            {
                public MethodBase MethodBase;
                public ParameterInfo[] Parameters;
                public Expression[] Args;
            }

            int FindBestMethod(IEnumerable<MethodBase> methods, Expression[] args, out MethodBase method)
            {
                MethodData[] applicable = methods.
                    Select(m => new MethodData { MethodBase = m, Parameters = m.GetParameters() }).
                    Where(m => IsApplicable(m, args)).
                    ToArray();
                if (applicable.Length > 1)
                {
                    applicable = applicable.
                        Where(m => applicable.All(n => m == n || IsBetterThan(args, m, n))).
                        ToArray();
                }
                if (applicable.Length == 1)
                {
                    MethodData md = applicable[0];
                    for (int i = 0; i < args.Length; i++) args[i] = md.Args[i];
                    method = md.MethodBase;
                }
                else
                {
                    method = null;
                }
                return applicable.Length;
            }

            bool IsApplicable(MethodData method, Expression[] args)
            {
                if (method.Parameters.Length != args.Length) return false;
                Expression[] promotedArgs = new Expression[args.Length];
                for (int i = 0; i < args.Length; i++)
                {
                    ParameterInfo pi = method.Parameters[i];
                    if (pi.IsOut) return false;
                    Expression promoted = PromoteExpression(args[i], pi.ParameterType, false);
                    if (promoted == null) return false;
                    promotedArgs[i] = promoted;
                }
                method.Args = promotedArgs;
                return true;
            }

            Expression PromoteExpression(Expression expr, Type type, bool exact)
            {
                if (expr.Type == type) return expr;
                if (expr is ConstantExpression)
                {
                    ConstantExpression ce = (ConstantExpression)expr;
                    if (ce == nullLiteral)
                    {
                        if (!type.IsValueType || IsNullableType(type))
                            return Expression.Constant(null, type);
                    }
                    else
                    {
                        string text;
                        if (literals.TryGetValue(ce, out text))
                        {
                            Type target = GetNonNullableType(type);
                            Object value = null;
                            switch (Type.GetTypeCode(ce.Type))
                            {
                                case TypeCode.Int32:
                                case TypeCode.UInt32:
                                case TypeCode.Int64:
                                case TypeCode.UInt64:
                                    value = ParseNumber(text, target);
                                    break;
                                case TypeCode.Double:
                                    if (target == typeof(decimal)) value = ParseNumber(text, target);
                                    break;
                                case TypeCode.String:
                                    value = ParseEnum(text, target);
                                    break;
                            }
                            if (value != null)
                                return Expression.Constant(value, type);
                        }
                    }
                }
                if (IsCompatibleWith(expr.Type, type))
                {
                    if (type.IsValueType || exact) return Expression.Convert(expr, type);
                    return expr;
                }
                return null;
            }

            static object ParseNumber(string text, Type type)
            {
                switch (Type.GetTypeCode(GetNonNullableType(type)))
                {
                    case TypeCode.SByte:
                        sbyte sb;
                        if (sbyte.TryParse(text, out sb)) return sb;
                        break;
                    case TypeCode.Byte:
                        byte b;
                        if (byte.TryParse(text, out b)) return b;
                        break;
                    case TypeCode.Int16:
                        short s;
                        if (short.TryParse(text, out s)) return s;
                        break;
                    case TypeCode.UInt16:
                        ushort us;
                        if (ushort.TryParse(text, out us)) return us;
                        break;
                    case TypeCode.Int32:
                        int i;
                        if (int.TryParse(text, out i)) return i;
                        break;
                    case TypeCode.UInt32:
                        uint ui;
                        if (uint.TryParse(text, out ui)) return ui;
                        break;
                    case TypeCode.Int64:
                        long l;
                        if (long.TryParse(text, out l)) return l;
                        break;
                    case TypeCode.UInt64:
                        ulong ul;
                        if (ulong.TryParse(text, out ul)) return ul;
                        break;
                    case TypeCode.Single:
                        float f;
                        if (float.TryParse(text, out f)) return f;
                        break;
                    case TypeCode.Double:
                        double d;
                        if (double.TryParse(text, out d)) return d;
                        break;
                    case TypeCode.Decimal:
                        decimal e;
                        if (decimal.TryParse(text, out e)) return e;
                        break;
                }
                return null;
            }

            static object ParseEnum(string name, Type type)
            {
                if (type.IsEnum)
                {
                    MemberInfo[] memberInfos = type.FindMembers(MemberTypes.Field,
                        BindingFlags.Public | BindingFlags.DeclaredOnly | BindingFlags.Static,
                        Type.FilterNameIgnoreCase, name);
                    if (memberInfos.Length != 0) return ((FieldInfo)memberInfos[0]).GetValue(null);
                }
                return null;
            }

            static bool IsCompatibleWith(Type source, Type target)
            {
                if (source == target) return true;
                if (!target.IsValueType) return target.IsAssignableFrom(source);
                Type st = GetNonNullableType(source);
                Type tt = GetNonNullableType(target);
                if (st != source && tt == target) return false;
                TypeCode sc = st.IsEnum ? TypeCode.Object : Type.GetTypeCode(st);
                TypeCode tc = tt.IsEnum ? TypeCode.Object : Type.GetTypeCode(tt);
                switch (sc)
                {
                    case TypeCode.SByte:
                        switch (tc)
                        {
                            case TypeCode.SByte:
                            case TypeCode.Int16:
                            case TypeCode.Int32:
                            case TypeCode.Int64:
                            case TypeCode.Single:
                            case TypeCode.Double:
                            case TypeCode.Decimal:
                                return true;
                        }
                        break;
                    case TypeCode.Byte:
                        switch (tc)
                        {
                            case TypeCode.Byte:
                            case TypeCode.Int16:
                            case TypeCode.UInt16:
                            case TypeCode.Int32:
                            case TypeCode.UInt32:
                            case TypeCode.Int64:
                            case TypeCode.UInt64:
                            case TypeCode.Single:
                            case TypeCode.Double:
                            case TypeCode.Decimal:
                                return true;
                        }
                        break;
                    case TypeCode.Int16:
                        switch (tc)
                        {
                            case TypeCode.Int16:
                            case TypeCode.Int32:
                            case TypeCode.Int64:
                            case TypeCode.Single:
                            case TypeCode.Double:
                            case TypeCode.Decimal:
                                return true;
                        }
                        break;
                    case TypeCode.UInt16:
                        switch (tc)
                        {
                            case TypeCode.UInt16:
                            case TypeCode.Int32:
                            case TypeCode.UInt32:
                            case TypeCode.Int64:
                            case TypeCode.UInt64:
                            case TypeCode.Single:
                            case TypeCode.Double:
                            case TypeCode.Decimal:
                                return true;
                        }
                        break;
                    case TypeCode.Int32:
                        switch (tc)
                        {
                            case TypeCode.Int32:
                            case TypeCode.Int64:
                            case TypeCode.Single:
                            case TypeCode.Double:
                            case TypeCode.Decimal:
                                return true;
                        }
                        break;
                    case TypeCode.UInt32:
                        switch (tc)
                        {
                            case TypeCode.UInt32:
                            case TypeCode.Int64:
                            case TypeCode.UInt64:
                            case TypeCode.Single:
                            case TypeCode.Double:
                            case TypeCode.Decimal:
                                return true;
                        }
                        break;
                    case TypeCode.Int64:
                        switch (tc)
                        {
                            case TypeCode.Int64:
                            case TypeCode.Single:
                            case TypeCode.Double:
                            case TypeCode.Decimal:
                                return true;
                        }
                        break;
                    case TypeCode.UInt64:
                        switch (tc)
                        {
                            case TypeCode.UInt64:
                            case TypeCode.Single:
                            case TypeCode.Double:
                            case TypeCode.Decimal:
                                return true;
                        }
                        break;
                    case TypeCode.Single:
                        switch (tc)
                        {
                            case TypeCode.Single:
                            case TypeCode.Double:
                                return true;
                        }
                        break;
                    default:
                        if (st == tt) return true;
                        break;
                }
                return false;
            }

            static bool IsBetterThan(Expression[] args, MethodData m1, MethodData m2)
            {
                bool better = false;
                for (int i = 0; i < args.Length; i++)
                {
                    int c = CompareConversions(args[i].Type,
                        m1.Parameters[i].ParameterType,
                        m2.Parameters[i].ParameterType);
                    if (c < 0) return false;
                    if (c > 0) better = true;
                }
                return better;
            }

            // Return 1 if s -> t1 is a better conversion than s -> t2
            // Return -1 if s -> t2 is a better conversion than s -> t1
            // Return 0 if neither conversion is better
            static int CompareConversions(Type s, Type t1, Type t2)
            {
                if (t1 == t2) return 0;
                if (s == t1) return 1;
                if (s == t2) return -1;
                bool t1t2 = IsCompatibleWith(t1, t2);
                bool t2t1 = IsCompatibleWith(t2, t1);
                if (t1t2 && !t2t1) return 1;
                if (t2t1 && !t1t2) return -1;
                if (IsSignedIntegralType(t1) && IsUnsignedIntegralType(t2)) return 1;
                if (IsSignedIntegralType(t2) && IsUnsignedIntegralType(t1)) return -1;
                return 0;
            }

            Expression GenerateEqual(Expression left, Expression right)
            {
                return Expression.Equal(left, right);
            }

            Expression GenerateNotEqual(Expression left, Expression right)
            {
                return Expression.NotEqual(left, right);
            }

            Expression GenerateGreaterThan(Expression left, Expression right)
            {
                if (left.Type == typeof(string))
                {
                    return Expression.GreaterThan(
                        GenerateStaticMethodCall("Compare", left, right),
                        Expression.Constant(0)
                    );
                }
                return Expression.GreaterThan(left, right);
            }

            Expression GenerateGreaterThanEqual(Expression left, Expression right)
            {
                if (left.Type == typeof(string))
                {
                    return Expression.GreaterThanOrEqual(
                        GenerateStaticMethodCall("Compare", left, right),
                        Expression.Constant(0)
                    );
                }
                return Expression.GreaterThanOrEqual(left, right);
            }

            Expression GenerateLessThan(Expression left, Expression right)
            {
                if (left.Type == typeof(string))
                {
                    return Expression.LessThan(
                        GenerateStaticMethodCall("Compare", left, right),
                        Expression.Constant(0)
                    );
                }
                return Expression.LessThan(left, right);
            }

            Expression GenerateLessThanEqual(Expression left, Expression right)
            {
                if (left.Type == typeof(string))
                {
                    return Expression.LessThanOrEqual(
                        GenerateStaticMethodCall("Compare", left, right),
                        Expression.Constant(0)
                    );
                }
                return Expression.LessThanOrEqual(left, right);
            }

            Expression GenerateAdd(Expression left, Expression right)
            {
                if (left.Type == typeof(string) && right.Type == typeof(string))
                {
                    return GenerateStaticMethodCall("Concat", left, right);
                }
                return Expression.Add(left, right);
            }

            Expression GenerateSubtract(Expression left, Expression right)
            {
                return Expression.Subtract(left, right);
            }

            Expression GenerateStringConcat(Expression left, Expression right)
            {
                return Expression.Call(
                    null,
                    typeof(string).GetMethod("Concat", new[] { typeof(object), typeof(object) }),
                    new[] { left, right });
            }

            MethodInfo GetStaticMethod(string methodName, Expression left, Expression right)
            {
                return left.Type.GetMethod(methodName, new[] { left.Type, right.Type });
            }

            Expression GenerateStaticMethodCall(string methodName, Expression left, Expression right)
            {
                return Expression.Call(null, GetStaticMethod(methodName, left, right), new[] { left, right });
            }

            void SetTextPos(int pos)
            {
                textPos = pos;
                ch = textPos < textLen ? text[textPos] : '\0';
            }

            void NextChar()
            {
                if (textPos < textLen) textPos++;
                ch = textPos < textLen ? text[textPos] : '\0';
            }

            void NextToken()
            {
                while (Char.IsWhiteSpace(ch)) NextChar();
                TokenId t;
                int tokenPos = textPos;
                switch (ch)
                {
                    case '!':
                        NextChar();
                        if (ch == '=')
                        {
                            NextChar();
                            t = TokenId.ExclamationEqual;
                        }
                        else
                        {
                            t = TokenId.Exclamation;
                        }
                        break;
                    case '%':
                        NextChar();
                        t = TokenId.Percent;
                        break;
                    case '&':
                        NextChar();
                        if (ch == '&')
                        {
                            NextChar();
                            t = TokenId.DoubleAmphersand;
                        }
                        else
                        {
                            t = TokenId.Amphersand;
                        }
                        break;
                    case '(':
                        NextChar();
                        t = TokenId.OpenParen;
                        break;
                    case ')':
                        NextChar();
                        t = TokenId.CloseParen;
                        break;
                    case '*':
                        NextChar();
                        t = TokenId.Asterisk;
                        break;
                    case '+':
                        NextChar();
                        t = TokenId.Plus;
                        break;
                    case ',':
                        NextChar();
                        t = TokenId.Comma;
                        break;
                    case '-':
                        NextChar();
                        t = TokenId.Minus;
                        break;
                    case '.':
                        NextChar();
                        t = TokenId.Dot;
                        break;
                    case '/':
                        NextChar();
                        t = TokenId.Slash;
                        break;
                    case ':':
                        NextChar();
                        t = TokenId.Colon;
                        break;
                    case '<':
                        NextChar();
                        if (ch == '=')
                        {
                            NextChar();
                            t = TokenId.LessThanEqual;
                        }
                        else if (ch == '>')
                        {
                            NextChar();
                            t = TokenId.LessGreater;
                        }
                        else
                        {
                            t = TokenId.LessThan;
                        }
                        break;
                    case '=':
                        NextChar();
                        if (ch == '=')
                        {
                            NextChar();
                            t = TokenId.DoubleEqual;
                        }
                        else
                        {
                            t = TokenId.Equal;
                        }
                        break;
                    case '>':
                        NextChar();
                        if (ch == '=')
                        {
                            NextChar();
                            t = TokenId.GreaterThanEqual;
                        }
                        else
                        {
                            t = TokenId.GreaterThan;
                        }
                        break;
                    case '?':
                        NextChar();
                        t = TokenId.Question;
                        break;
                    case '[':
                        NextChar();
                        t = TokenId.OpenBracket;
                        break;
                    case ']':
                        NextChar();
                        t = TokenId.CloseBracket;
                        break;
                    case '|':
                        NextChar();
                        if (ch == '|')
                        {
                            NextChar();
                            t = TokenId.DoubleBar;
                        }
                        else
                        {
                            t = TokenId.Bar;
                        }
                        break;
                    case '"':
                    case '\'':
                        char quote = ch;
                        do
                        {
                            NextChar();
                            while (textPos < textLen && ch != quote) NextChar();
                            if (textPos == textLen)
                                throw ParseError(textPos, Res.UnterminatedStringLiteral);
                            NextChar();
                        } while (ch == quote);
                        t = TokenId.StringLiteral;
                        break;
                    default:
                        if (Char.IsLetter(ch) || ch == '@' || ch == '_')
                        {
                            do
                            {
                                NextChar();
                            } while (Char.IsLetterOrDigit(ch) || ch == '_');
                            t = TokenId.Identifier;
                            break;
                        }
                        if (Char.IsDigit(ch))
                        {
                            t = TokenId.IntegerLiteral;
                            do
                            {
                                NextChar();
                            } while (Char.IsDigit(ch));
                            if (ch == '.')
                            {
                                t = TokenId.RealLiteral;
                                NextChar();
                                ValidateDigit();
                                do
                                {
                                    NextChar();
                                } while (Char.IsDigit(ch));
                            }
                            if (ch == 'E' || ch == 'e')
                            {
                                t = TokenId.RealLiteral;
                                NextChar();
                                if (ch == '+' || ch == '-') NextChar();
                                ValidateDigit();
                                do
                                {
                                    NextChar();
                                } while (Char.IsDigit(ch));
                            }
                            if (ch == 'F' || ch == 'f') NextChar();
                            break;
                        }
                        if (textPos == textLen)
                        {
                            t = TokenId.End;
                            break;
                        }
                        throw ParseError(textPos, Res.InvalidCharacter, ch);
                }
                token.id = t;
                token.text = text.Substring(tokenPos, textPos - tokenPos);
                token.pos = tokenPos;
            }

            bool TokenIdentifierIs(string id)
            {
                return token.id == TokenId.Identifier && String.Equals(id, token.text, StringComparison.OrdinalIgnoreCase);
            }

            string GetIdentifier()
            {
                ValidateToken(TokenId.Identifier, Res.IdentifierExpected);
                string id = token.text;
                if (id.Length > 1 && id[0] == '@') id = id.Substring(1);
                return id;
            }

            void ValidateDigit()
            {
                if (!Char.IsDigit(ch)) throw ParseError(textPos, Res.DigitExpected);
            }

            void ValidateToken(TokenId t, string errorMessage)
            {
                if (token.id != t) throw ParseError(errorMessage);
            }

            void ValidateToken(TokenId t)
            {
                if (token.id != t) throw ParseError(Res.SyntaxError);
            }

            Exception ParseError(string format, params object[] args)
            {
                return ParseError(token.pos, format, args);
            }

            Exception ParseError(int pos, string format, params object[] args)
            {
                return new ParseException(string.Format(System.Globalization.CultureInfo.CurrentCulture, format, args), pos);
            }

            static Dictionary<string, object> CreateKeywords()
            {
                Dictionary<string, object> d = new Dictionary<string, object>(StringComparer.OrdinalIgnoreCase);
                d.Add("true", trueLiteral);
                d.Add("false", falseLiteral);
                d.Add("null", nullLiteral);
                d.Add(keywordIt, keywordIt);
                d.Add(keywordIif, keywordIif);
                d.Add(keywordNew, keywordNew);
                foreach (Type type in predefinedTypes) d.Add(type.Name, type);
                return d;
            }
        }

        static class Res
        {
            public const string DuplicateIdentifier = "The identifier '{0}' was defined more than once";
            public const string ExpressionTypeMismatch = "Expression of type '{0}' expected";
            public const string ExpressionExpected = "Expression expected";
            public const string InvalidCharacterLiteral = "Character literal must contain exactly one character";
            public const string InvalidIntegerLiteral = "Invalid integer literal '{0}'";
            public const string InvalidRealLiteral = "Invalid real literal '{0}'";
            public const string UnknownIdentifier = "Unknown identifier '{0}'";
            public const string NoItInScope = "No 'it' is in scope";
            public const string IifRequiresThreeArgs = "The 'iif' function requires three arguments";
            public const string FirstExprMustBeBool = "The first expression must be of type 'Boolean'";
            public const string BothTypesConvertToOther = "Both of the types '{0}' and '{1}' convert to the other";
            public const string NeitherTypeConvertsToOther = "Neither of the types '{0}' and '{1}' converts to the other";
            public const string MissingAsClause = "Expression is missing an 'as' clause";
            public const string ArgsIncompatibleWithLambda = "Argument list incompatible with lambda expression";
            public const string TypeHasNoNullableForm = "Type '{0}' has no nullable form";
            public const string NoMatchingConstructor = "No matching constructor in type '{0}'";
            public const string AmbiguousConstructorInvocation = "Ambiguous invocation of '{0}' constructor";
            public const string CannotConvertValue = "A value of type '{0}' cannot be converted to type '{1}'";
            public const string NoApplicableMethod = "No applicable method '{0}' exists in type '{1}'";
            public const string MethodsAreInaccessible = "Methods on type '{0}' are not accessible";
            public const string MethodIsVoid = "Method '{0}' in type '{1}' does not return a value";
            public const string AmbiguousMethodInvocation = "Ambiguous invocation of method '{0}' in type '{1}'";
            public const string UnknownPropertyOrField = "No property or field '{0}' exists in type '{1}'";
            public const string NoApplicableAggregate = "No applicable aggregate method '{0}' exists";
            public const string CannotIndexMultiDimArray = "Indexing of multi-dimensional arrays is not supported";
            public const string InvalidIndex = "Array index must be an integer expression";
            public const string NoApplicableIndexer = "No applicable indexer exists in type '{0}'";
            public const string AmbiguousIndexerInvocation = "Ambiguous invocation of indexer in type '{0}'";
            public const string IncompatibleOperand = "Operator '{0}' incompatible with operand type '{1}'";
            public const string IncompatibleOperands = "Operator '{0}' incompatible with operand types '{1}' and '{2}'";
            public const string UnterminatedStringLiteral = "Unterminated string literal";
            public const string InvalidCharacter = "Syntax error '{0}'";
            public const string DigitExpected = "Digit expected";
            public const string SyntaxError = "Syntax error";
            public const string TokenExpected = "{0} expected";
            public const string ParseExceptionFormat = "{0} (at index {1})";
            public const string ColonExpected = "':' expected";
            public const string OpenParenExpected = "'(' expected";
            public const string CloseParenOrOperatorExpected = "')' or operator expected";
            public const string CloseParenOrCommaExpected = "')' or ',' expected";
            public const string DotOrOpenParenExpected = "'.' or '(' expected";
            public const string OpenBracketExpected = "'[' expected";
            public const string CloseBracketOrCommaExpected = "']' or ',' expected";
            public const string IdentifierExpected = "Identifier expected";
        }
    }
